Block interleaving is effective as a countermeasure against burst errors.
Hereinafter, block interleaving will be described taking satellite broadcasting as an example. A radio wave from a broadcast station on earth is transmitted to a satellite, relayed by the satellite, and received by a satellite broadcast receiver provided at home.
The radio wave, which is transmitted from the broadcast station through the satellite to home, might be subjected to interference by thunder, rain or the like in the transmission path. While the radio wave is subjected to such interference, errors occur in data. These errors are called “burst errors”.
In digital transmission, since information for error correction has already been added to the original data, errors can be corrected so long as the errors are within a predetermined number of bits in each segment. However, continuous errors such as burst errors cannot be corrected.
So, data to be transmitted is temporally dispersed in advance (a method for this data dispersion is block interleaving), whereby, even if burst errors occur during transmission, these burst errors are also dispersed when the temporal positions of the dispersed data are recovered at the receiving end (a method for this recovery is block deinterleaving) and, in each data block, the burst errors can be limited within a number of bits which can be corrected.
When performing such block interleaving and block deinterleaving, two planes of storage units, each having a storage area of 1 block (L×M data) originally, are required, and writing and reading are alternately repeated on these storage units. Japanese Published Patent Application No. Hei.8-511393 discloses block interleaving and block deinterleaving which can be realized with reduced circuit scale and reduced power consumption.
FIG. 13 is a diagram schematically illustrating the operation of the conventional block interleaving, wherein, for simplification, block interleaving is performed on 4 rows×5 columns of data.
Assuming that addresses of a storage unit of a block interleaving apparatus are allocated as shown in FIG. 13(a), initially, an address increment REG is set at 1, and data are sequentially written in the order of 0→1→2→ . . . . →19, i.e., in the order as the address increments one by one. Next, as shown in FIG. 13(b), data are read out in the order as the address increments five by five. That is, the REG is multiplied by 5, and an address which increments by 5 at every data input is successively generated with address 0 shown in FIG. 13(a) being an initial value. At this time, when the address exceeds 19 (=4×5−1), the remainder over 19 is used as an address. Then, according to the addresses generated under this address generation rule, initially, the data which have already been written as shown in FIG. 13(a) are read out in the order of the generated addresses as shown in FIG. 13(b) and, after the readout is completed, data are written in the same addresses and in the same order as those for the data reading shown in FIG. 13(b).
Next, as shown in FIG. 13(c), the REG is multiplied by 5, and when the value (=25) exceeds 19, the remainder over 19 is used as the value of REG.
Then, using the address arrangement shown in FIG. 13(a) as a reference and address 0 as an initial value, an address which increments by 6 (=25−19) for every input data is successively generated as shown in FIG. 13(c) and, when the address exceeds 19 (=4×5−1), reading is carried out using the remainder over 19 as an address. After the reading is completed in FIG. 13(c), data are written in the same addresses and in the same order as those for the reading.
Thereafter, by repeating the same process as described above, reading is carried out in different address orders, and writing is performed on the same addresses and in the same order as those for the reading, whereby, in this example, the address order returns to that of FIG. 13(a) at the point of time shown in FIG. 13(j).
By repeating the above-described procedure, it is possible to perform block interleaving using a RAM 202 having a storage area of one block (L×M data), as shown in FIG. 14. The block interleaving is realized by contriving, as described above, the writing/reading control by the RAM control apparatus 200 and the addresses generated by the address generation unit 201.
The address generation rule employed in the conventional block interleaving apparatus is as follows.
That is, assuming that the n-th address is Ab(n), the number of rows of the storage unit is L, the number of columns is M, b is an integer not less than 0, and x is an arbitrary integer not less than 0 and not larger than b,Ab(n)=(Ab(n−1)+M**(b−x))mod(L×M−1)  (1)Further,REG=(M**(b−x))mod(L×M−1)wherein Ab(0) is 0, and M**(b−x) indicates the (b−x)th power of M. The formula “L×M−1” herein means “(L×M)−1”.
Further, block deinterleaving is performed as follows on the data which have been subjected to the above-described block interleaving. Assuming that addresses of a storage unit of a block deinterleaving apparatus are allocated as shown in FIG. 13(k), initially, the REG is set at 1, and data are sequentially written in the addresses in the order of 0→1→2→ . . . →19, i.e., according to the one-by-one increment of the addresses. Next, as shown in FIG. 13(1), the data are read out according to four-by-four increment of the addresses. That is, the REG is multiplied by 4, and an address which increases by 4 for every input data is sequentially generated, with address 0 shown in FIG. 13(k) being an initial value. At this time, when the address exceeds 19 (=4×5−1), the remainder over 19 is used as an address. Then, according to the addresses generated under this address generation rule, initially, the data which have already been written as shown in FIG. 13(k) are sequentially read out in the order of the generated addresses as shown in FIG. 13(1). After the readout has been completed, data writing is performed on the same addresses and in the same order as those for the readout shown in FIG. 13(1).
Next, as shown in FIG. 13(m), the REG is multiplied by 4, and when the product exceeds 19, the remainder over 19 is used as the value of REG. In this case, since the REG value 16 is smaller than 19, this value 16 is used as it is.
Then, an address which increments by 16 for every input data is sequentially generated by using the address arrangement shown in FIG. 13(k) as a reference, and address 0 as an initial value, and when the address exceeds 19 (=4×5−1), reading is carried out using the remainder over 19 as an address. After the reading has been completed in FIG. 13(m), data are written in the same addresses and in the same order as those for the reading.
By repeating the same process as above, reading is sequentially carried out in different address orders, and writing is performed on the same addresses and in the same order as those for the reading, whereby the address order returns to that shown in FIG. 13(k) at the point of time shown in FIG. 13(t).
By repeating the above-described procedure, it is possible to perform block deinterleaving by using a RAM 202 having a storage area of one block (L×M data), as shown in FIG. 14. This block deinterleaving is realized by contriving, as described above, the writing/reading control by the RAM control apparatus 200 and the addresses generated by the address generation unit 201.
The address generation rule employed in the conventional block deinterleaving apparatus is as follows.Ab(n)=(Ab(n−1)+L**(b−x))mod(L×M−1)  (2)Further,REG=(L**(b−x))mod(L−M−1)wherein Ab(0) is 0.
In formula (2), M in formula (1) is changed to L.
The conventional block interleaving apparatus and block deinterleaving apparatus are constructed as described above, and these apparatuses can perform block interleaving and block deinterleaving by using only one storage unit having a storage area corresponding to one block, whereby reduced circuit scale and low power consumption are realized.
However, the conventional block interleaving apparatus and block deinterleaving apparatus are desired to be smaller in scale and lower in power consumption with regard to the cost and power consumption and, therefore, further reductions in circuit scale and power consumption are desired.
The present invention has for its object to provide a block interleaving apparatus, a block deinterleaving apparatus, a block interleaving method, and the block deinterleaving method, which can realize further reduction in circuit scale and further reduction in power consumption, by optimizing control units for storage units.